1. Field of the Invention
The present invention generally relates to methods of allocating functions to memory space, and particularly relates to a cache coloring method that allocates functions to memory space such as to reduce the possibility of cache conflict.
2. Description of the Related Art
In computer systems, generally, high-speed, small capacity cache memories are provided in addition to main memories. A portion of the information stored in the main memories is copied to a cache. When this information is accessed, the information is retrieved from the cache rather than from the main memories, thereby achieving high-speed information retrieval.
As caches are capable of high-speed operations and thus more expensive than main memories, their storage capacity is very small. A cache contains a plurality of cache lines, and the copying of information from external memory (main memory) to the cache is performed on a cache-line-by-cache-line basis. Because of this, the memory space of the external memory is divided in the units of cache lines, and the divided memory areas are successively allocated to the cache lines in advance. Since the capacity of the cache is smaller than the capacity of the external memory, the memory areas of the external memory are repeatedly allocated to the same cache lines.
When an access is first made to a given address, information (data or a program) stored in this address is copied to a corresponding cache line in the cache. When a next access is made to the same address, the information is directly retrieved from the cache.
When program functions are to be executed, different program functions allocated to different addresses in the external memory may be allocated to the same cache line. In this case, one of the program functions needs to be copied to the cache at every turn when the program functions are alternately called. This is referred to as cache conflict. The problem is that the more frequent the occurrence of cache conflict, the slower the execution speed of the programs is. In order to obviate this problem, it is preferable to avoid allocating functions having the high likelihood of simultaneous executions to the same cache line, and research efforts have been made to this end.
Caches include an instruction cache and a data cache. The above-noted problem of function retrieval occurs with respect to the instruction cache. Methods of mapping cache memory generally include a direct method, a set-associative method, and a full-associative method. When considering the above-noted problem of cache conflict, it does not matter which one of these three methods is employed. In the following description, thus, the direct map method will be used as an example.
In order to obviate the problem of cache conflict, the strength of function is defined as an indication of the number of calls between functions and the number of calls of a specific function-calling pattern. In the related art, there is a method by which functions having the great strength of function (i.e., there is a high possibility of the functions calling each other) are not allocated to the same cache line. Setting and modifying of link sequences on a function-specific basis for the purpose of reducing cache conflict and instruction cache miss is called cache coloring.
Patent Documents No. 1 through No. 3 disclose methods of allocating codes in a descending order of the number of calls. Patent Document No. 4 discloses a method of reducing cache conflict. In this method, information about a time series of functions is extracted, and the patterns of execution of function combinations by which cache conflict may possibly occur are detected based on the time-series information in addition to the direct calling of functions such as consecutive calling of functions. Cache conflict is then reduced by using the number of executions of a pattern in which a plurality of functions are consecutively called from a given function or called within a loop. Patent Document No. 5 discloses a method that obtains, through tentative allocation, patterns executed a large number of times among specific patterns in which a plurality of functions are consecutively called from a given function or called within a loop. Patent Document No. 6 discloses a method by which functions called by a loop having high frequency of execution are successively allocated by generating and referring to the a structure graph.                [Patent Document No. 1] Japanese Patent Application Publication No. 5-324281        [Patent Document No. 2] Japanese Patent Application Publication No. 7-84799        [Patent Document No. 3] Japanese Patent Application Publication No. 8-328870        [Patent Document No. 4] Japanese Patent Application Publication No. 2001-216140        [Patent Document No. 5] Japanese Patent Application Publication No. 2001-282547        [Patent Document No. 6] Japanese Patent No. 3309810        [Non-patent Document No. 1] Keisuke Hashimoto, Hideki Ando, Toshio Shimada, “Reallocation of codes in the Units of Basic Blocks for Reduction of Instruction Cache Miss,” 1999 Parallel Processing Symposium, JSPP'99, June of 1999, pp. 31-38        